﻿//题目描述
//小明有一个容量为V 的背包。
//这天他去商场购物，商场一共有N 件物品，第i 件物品的体积为wi​，价值为vi​。
//小明想知道在购买的物品总体积不超过V 的情况下所能获得的最大价值为多少，请你帮他算算。
//输入描述
//输入第1 行包含两个正整数N, V，表示商场物品的数量和小明的背包容量。
//第2∼N + 1 行包含2 个正整数w, v，表示物品的体积和价值。1≤N≤10^2，1≤V≤10^3，1≤𝑤𝑖,𝑣𝑖≤10^3。
//输出描述
//输出一行整数表示小明所能获得的最大价值。
//输入输出样例
//示例 1
//输入
//5 20
//1 6
//2 5
//3 8
//5 15
//3 3
//输出
//37
#include<bits/stdc++.h>
using namespace std;
const int N = 1e3 + 9;
int dp[N];
int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int N, V;
	cin >> N >> V;
	for (int i = 1; i <= N; i++) {
		int w, v;
		dp[0] = dp[1] = 0;
		cin >> w >> v;
		for (int j = V; j >= w; j--) {
			dp[j] = max(dp[j], dp[j - w] + v);
		}
	}
	cout << dp[V];
	return 0;
}